package LearnDataStructure.c_树结构.有序树.二叉树;
/**
 * @author wuqiu
 *	子节点 root * 2 + 1
 *	父节点 (child - 1) / 2    除法向下取整
 *
 *	完全二叉树：除了叶子节点每个节点都有两个孩子
 *	近似完全二叉树：仅仅比完全二叉树少最后一个孩子
 */
public class a_MyBinaryTreebyArray {
	public static void main(String[] args) {
		int[] arr = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
		preOrder(arr, 0);
		System.out.println("----");
		inOrder(arr, 0);
		System.out.println("----");
		aftOrder(arr, 0);
	}
	
	/**
	 * 先序遍历
	 * @param arr
	 * @param root
	 */
	public static void preOrder(int[] arr, int root) {
		if (root >= arr.length) {
			return;
		}
		System.out.println(arr[root]);
		preOrder(arr, root * 2 + 1);
		preOrder(arr, root * 2 + 2);
	}
	
	/**
	 * 中序遍历
	 * @param arr
	 * @param root
	 */
	public static void inOrder(int[] arr, int root) {
		if (root >= arr.length) {
			return;
		}
		inOrder(arr, root * 2 + 1);
		System.out.println(arr[root]);
		inOrder(arr, root * 2 + 2);
	}
	
	/**
	 * 后序遍历
	 * @param arr
	 * @param root
	 */
	public static void aftOrder(int[] arr, int root) {
		if (root >= arr.length) {
			return;
		}
		aftOrder(arr, root * 2 + 1);
		aftOrder(arr, root * 2 + 2);
		System.out.println(arr[root]);
	}
}
